二维数组的查找

2023-03-15 21:20| 来源: 网络整理| 查看: 265

牛客网链接：二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

题目要求：

提供一个二维数组array，其每行顺序按照从左往右从小到大排序，每列顺序从上到下从大到小排序，现要求我们完成一个函数，输入一个整数target，并判断数组中是否有这个数。

此时先假设一个数组：

int main() { int arr[5][5] = {{1,2,3,4,5},{11,12,13,14,15},{21,22,23,24,25} {31,32,33,34,35},{41,42,43,44,45}}; int target = 0; scanf("%d",&target); if(Find(***,***...)) printf("yes\n"); return 0; }

满足上述条件后，就可以开始着手写函数了(函数参数待定这里用**表示)，完成这个Find函数，可以从几个解题思路入手：

1.暴力枚举 int Find(int arr[5][5], int n) { //遍历数组 for(int i = 0;i < 5 ; i++) { for(int j = 0 ; j < 5 ; j++ ) { //arr[i][j]等于n直接返回true if(arr[i][j] == n) return 1; } } //遍历了一遍数组函数还没结束，说明数组中没有这个数 return 0; }

但是当数组超级大时，运算量会极大极大，会给电脑带来很大的负荷。因此需要一个能带来效率的算法来实现；

2.利用数组特性

我们仔细分析，不难发现，对于杨氏矩阵老说，右上角和左下角的元素是有特点的。右上角的元素是一行中最大的，一列中最小的。左下角的元素是一行中最小的，是一列中最大的。所以我们可以从右上角或者左下角开始查找。比如：从右上角开始查找的时候，右上角的元素比我们要查找元素小，我们就可以去掉右上角元素所在的这一行；右上角的元素比我们要查找的元素大，我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的，所以时间复杂度是小于O(N)，也满足题目要求。

int Find(int arr[][5] ,int x ,int y ,int n) { int i = 0, j = y - 1; //从右上角开始遍历 while (j >= 0 && i < x) { if (a[i][j] < f) //比我大就向下 { i++; } else if (a[i][j] > f) //比我小就向左 { j--; } else { return 1; } } return 0; }

此时函数实参传递x = 5, y = 5,具体情况还要看矩阵的尺寸大小。

可以看到程序直接拿每行的最后一个元素与target相比较，则可以节省去很大一部分时间。

3.二分查找：

二分查找的示例在之前已经讲过，与之不同的是，这次的二分查找应用在二维数组上，对此有不理解的可以翻阅我往期的文章，在这里不做过多介绍：；

往期我们知道二分查找有一个严苛的条件，那就是数组必须按照顺序排列，而在满足条件的情况下使用二分查找无疑可以大大提高运算效率；

思路：

首先找到中间数，如果中间数大于要找的target，就在其上和其右查找，当本行数组第一个元素大于target时，就让矩阵的下限拉到中间行的上一行，然后重复以上步骤；当本行数组第一个元素小于target时，就让矩阵的最右端拉到中间列的前一个坐标。同理，中间数小于要找的target，操作就反正来😊。

上代码：

int Find(arr[][5],int n) { int up = 0, down = 5; int left = 0, right = 5; int flag = 1; int row_rid = up + (down - up) / 2; int col_rid = left + (right - left) / 2; while (left n) down = row_rid - 1; //在行里二分查找 else right = col_rid; } else if (arr[row_rid][col_rid] < n) { if (arr[row_rid][ROW - 1] < n) up = row_rid + 1; //在行里二分查找 else left = col_rid; } else { printf("yes\n"); flag = 0; break; } } else { printf("no\n"); flag = 0; break; } row_rid = up + (down - up) / 2; col_rid = left + (right - left) / 2; } if (flag) printf("no\n"); }

这就是大概的思路啦，还有其他新奇的思路欢迎下方留言，大家互相学习相互支持哦。😊😊😊😊

【本文地址】

公司简介

联系我们